/**
*	@file Parser.cpp
*
*	@brief parse the SIMPLE program
*
*	@author li yuchen
*
*	@date 1/28/2011
*/

#include "Parser.h"
#include "Utility.h"
#include "ConstTable.h"
#include <fstream>
#include <iostream>
using namespace std;

/* ------------------------------------------------- type declare ---------------------------------------------- */

// the token type of each token taken from the program
static enum ParserTokenType{
	VARIABLE,CONSTANT,
	ADD,MINUS,MULTIPLY,EQUAL,
	SEMICOLON,CURLY_BRACKET_L,CURLY_BRACKET_R,ROUND_BRACKET_L,ROUND_BRACKET_R,
	// END program
	START,END
};

// indict which part of parser detect error
static enum ErrorType{
	FILE_ERROR,
	TOKEN_ERROR,
	PROC_ERROR,STMTLIST_ERROR,STMT_ERROR,
	ASSIGN_ERROR,CALL_ERROR,WHILE_ERROR,IF_ERROR,EXPR_ERROR,
};

/* ------------------------------------------------- function declare ------------------------------------------- */

static TNode* MatchProcedure();
// parent is useful when it is a while or if for setting parent child relationship
static TNode* MatchStmtList(TNode* parent);
static TNode* MatchStmt();
static TNode* MatchCall();
static TNode* MatchWhile();
static TNode* MatchIf();
static TNode* MatchAssign();
static TNode* MatchExpr(TNode* assign_tnode);
static TNode* MatchOp();
static TNode* MatchVar();
static TNode* MatchConstant();

// get a token from the program text string which delares below
static void GetToken();
// when there is syntax error, call this function and pass the error type
// program will exit after this call
static void parser_exit(ErrorType error_type);



/* ------------------------------------------------- variable declare ------------------------------------------- */

// program_text will hold the entire SIMPLE program;
static string parser_program_text;
// this will hold every token
static string parser_token;
// this will indicate the token type
static ParserTokenType parser_token_type = START;
// describe the current position of the string
static unsigned int parser_current_position = 0;
// keep track of the statement number
static StmtNum parser_stmt_num = 0;
// keep track of the current procedure
static string parser_current_proc;


// for drawing AST
static int parser_stmtlist_count = 0;
static int parser_var_count = 0;
static int parser_const_count = 0;
static int parser_op_count = 0;

/* ------------------------------------------------- function implementation ------------------------------------------- */

void Parse(string filename){

	// get the input file stream
	ifstream input_file(filename,ios::in);

	string program_line = "";

	// read the entire program in program_text
	if (input_file.is_open()){
		while(input_file.good()){
			getline(input_file,program_line);
			if(program_line.empty()) continue;
			parser_program_text.append(" ");
			parser_program_text.append(program_line);
		}
	}
	else parser_exit(FILE_ERROR);

	// close the file
	input_file.close();

	TNode* ast_root = AST::get_p_tnode_AST_root();
	TNode* proc1_tnode = NULL;
	TNode* proc2_tnode = NULL;

	GetToken();
	proc1_tnode = MatchProcedure();
	AST::SetParent(ast_root,proc1_tnode);

	while(1){
		GetToken();
		if(parser_token_type == END) break;

		proc2_tnode = MatchProcedure();
		AST::SetSibling(proc1_tnode,proc2_tnode);
		proc1_tnode = proc2_tnode;
	}
	return;
}

// step 1: retrieve the next token and check wether it has a procedure identifier and 
// step 2: retrieve the procedure name and add it into procedure table 
// step 3: create the TNode for this procedure and set the root in the proc table
// step 4: record the start statement number for procedure and match the StmtList pattern
// step 5: create the link between stmtlist and the procedure
// step 6: set procedure range
TNode* MatchProcedure(){
	// step 1:
	if(parser_token != "procedure") parser_exit(PROC_ERROR);

	// step 2:
	GetToken();
	if(parser_token_type != VARIABLE) parser_exit(PROC_ERROR);
	parser_current_proc = parser_token;
	int proc_index = ProcTable::InsertProc(parser_token);
	/* TODO error check if duplicate procedure */

	// step 3:
	TNode* procedure_tnode = AST::CreateTNode(PROC_TYPE,proc_index,NOT_APPLICABLE);
	ProcTable::SetProcASTRoot(proc_index,procedure_tnode);

	// step 4:
	int proc_start_stmt_line = parser_stmt_num + 1;
	TNode* stmtlist_tnode = MatchStmtList(NULL);

	// step 5:
	AST::SetParent(procedure_tnode,stmtlist_tnode);

	// step 6:
	ProcTable::SetStmtNumRange(proc_index,proc_start_stmt_line,parser_stmt_num);
	return procedure_tnode;
}

// step 1: match "{"
// step 2: match the first statment for this stmtlist
// step 3: match the remaining possible statement for this stmtlist
TNode* MatchStmtList(TNode* parent){

	// step 1:
	GetToken();
	if(parser_token != "{") parser_exit(PROC_ERROR); 

	TNode* stmt1_tnode = NULL;
	TNode* stmt2_tnode = NULL;
	TNode* stmtlist_tnode = AST::CreateTNode(STMT_LIST_TYPE,NOT_APPLICABLE,parser_stmtlist_count);
	parser_stmtlist_count++;
	
	// step 2:
	GetToken();
	stmt1_tnode = MatchStmt();
	// set parent link for TNode
	AST::SetParent(stmtlist_tnode,stmt1_tnode);
	// insert into parent table
	if(parent != NULL) Parent::SetParent(parent->stmt_num,stmt1_tnode->stmt_num);

	// step 2:
	while(1){
		GetToken();
		// end of statement list
		if(parser_token == "}") break;

		stmt2_tnode = MatchStmt();
		// set the sibling relationship
		AST::SetSibling(stmt1_tnode,stmt2_tnode);
		// insert into parent table
		if(parent != NULL) Parent::SetParent(parent->stmt_num,stmt2_tnode->stmt_num);
		stmt1_tnode = stmt2_tnode;
	}
	return stmtlist_tnode;
}

TNode* MatchStmt(){
	TNode* stmt_tnode = NULL;
	
	// check if it is a valid statement
	if(parser_token_type != VARIABLE) parser_exit(STMT_ERROR);

	if(parser_token == "while") stmt_tnode = MatchWhile();
	else if(parser_token == "if") stmt_tnode = MatchIf();
	else if(parser_token == "call") stmt_tnode = MatchCall();
	else stmt_tnode = MatchAssign();

	return stmt_tnode;
}

// no need to match where clause since we have already check it and create the TNode for while
// step 1: increase the statement count and create the tnode while insert into stmt table
// step 2: match control variable
// step 3: match statment list
// step 4: set the sibling link between control_proc_node with stmt_list
TNode* MatchWhile(){
	// step 1:
	parser_stmt_num++;
	TNode* while_tnode = AST::CreateTNode(WHILE_TYPE,NOT_APPLICABLE,parser_stmt_num);
	StmtTable::AddStmtEntry(parser_stmt_num,while_tnode);

	// step 2:
	GetToken();
	if(parser_token_type != VARIABLE) parser_exit(WHILE_ERROR);
	TNode* control_var_tnode = MatchVar();
	AST::SetParent(while_tnode,control_var_tnode);

	// step 3:
	TNode* stmtlist_tnode = MatchStmtList(while_tnode);

	// step 4:
	AST::SetSibling(control_var_tnode,stmtlist_tnode);

	return while_tnode;

}

// no need to match where clause since we have already check it and create the TNode for while
// step 1: increase the statement count and create the tnode if insert into stmt table
// step 2: match control variable
// step 3: match the first stmtlist and 
// step 4: match "else" and stmtlist
// step 5: set the relationship between if clause, control variable and two stmtlist
TNode* MatchIf(){
	// step 1:
	parser_stmt_num++;
	TNode* if_tnode = AST::CreateTNode(IF_TYPE,NOT_APPLICABLE,parser_stmt_num);
	StmtTable::AddStmtEntry(parser_stmt_num,if_tnode);

	// step 2:
	GetToken();
	if(parser_token_type != VARIABLE) parser_exit(IF_ERROR); 
	TNode* control_var_tnode = MatchVar();
	AST::SetParent(if_tnode,control_var_tnode);

	// step 3:
	GetToken();
	if(parser_token != "then") parser_exit(IF_ERROR);
	TNode* stmtlist_tnode_1 = MatchStmtList(if_tnode);

	// step 4:
	GetToken();
	if(parser_token != "else") parser_exit(IF_ERROR); 
	TNode* stmtlist_tnode_2 = MatchStmtList(if_tnode);

	// step 5:
	AST::SetSibling(control_var_tnode,stmtlist_tnode_1);
	AST::SetSibling(stmtlist_tnode_1,stmtlist_tnode_2);

	return if_tnode;
}

TNode* MatchCall(){
	parser_stmt_num++;
	GetToken();
	if(parser_token_type != VARIABLE) parser_exit(ASSIGN_ERROR); 
	TNodeValue callee_index = ProcTable::InsertCallee(parser_current_proc,parser_token);
	TNode* call_tnode = AST::CreateTNode(CALL_TYPE,callee_index,parser_stmt_num);
	StmtTable::AddStmtEntry(parser_stmt_num,call_tnode);

	GetToken();
	if(parser_token != ";") parser_exit(ASSIGN_ERROR); 
	return call_tnode;
}

// step 1: increase the statement count and create the tnode assign insert into stmt table
// step 2: match the modified variable and  set the link between the variable and assignment
// step 3: set the modifies relationship after that match =
// step 4: match expr
// step 5: set the link between assign_var and the expr
TNode* MatchAssign(){
	// step 1:
	parser_stmt_num++;
	TNode* assign_tnode = AST::CreateTNode(ASSIGN_TYPE,NOT_APPLICABLE,parser_stmt_num);
	StmtTable::AddStmtEntry(parser_stmt_num,assign_tnode);
	
	// step 2:
	TNode* assign_var_tnode = MatchVar();
	AST::SetParent(assign_tnode,assign_var_tnode);
	// insert into modifies table
	Modifies::SetModifiesA(parser_stmt_num,assign_var_tnode->value);

	// step 3:
	GetToken();
	if(parser_token != "=") parser_exit(ASSIGN_ERROR);

	// step 4:
	TNode* expr_tnode = MatchExpr(assign_tnode);

	// step 5:
	AST::SetSibling(assign_var_tnode,expr_tnode);
	
	return assign_tnode;
}

// step 1: check this procedure name exist in variable table, if not added
// step 2: create the tnode for this variable
TNode* MatchVar(){
	// step 1:
	int var_index = VarTable::InsertVar(parser_token);

	// step 2:
	TNode* var_tnode = AST::CreateTNode(VAR_TYPE,var_index,parser_var_count);
	parser_var_count++;
	return var_tnode;
}

TNode* MatchConstant(){
	TNode* const_tnode = AST::CreateTNode(CONST_TYPE, atoi(parser_token.c_str()),parser_const_count);
	parser_const_count++;
	ConstTable::InsertConst(const_tnode->value);
	return const_tnode;
}

TNode* MatchOp(){
	TNode* op_tnode = AST::CreateTNode(OP_TYPE,parser_token.at(0),parser_op_count);
	parser_op_count++;
	return op_tnode;
}

TNode* MatchExpr(TNode* assign_tnode){
	GetToken();
	if(parser_token == ";") parser_exit(EXPR_ERROR);

	// stack for building up the AST
	stack<TNode*> var_stack;
	stack<TNode*> op_stack;

	// local TNode variable to build the AST
	TNode* var_current = NULL;
	TNode* cons_current = NULL;
	TNode* op_current = NULL;
	TNode* op_top = NULL;
	TNode* var1 = NULL;
	TNode* var2 = NULL;

	// phase to build the stack
	while(parser_token != ";"){
		switch(parser_token_type){
		case VARIABLE:
			var_current = MatchVar();
			// insert into uses table
			Uses::SetUsesA(assign_tnode->stmt_num,var_current->value);
			var_stack.push(var_current);
			GetToken();
			break;
		case CONSTANT:
			cons_current = MatchConstant();
			var_stack.push(cons_current);
			GetToken();
			break;
		case ADD:
		case MINUS:
		case MULTIPLY:
			 op_current = MatchOp();
			 if(op_stack.empty()){
				 op_stack.push(op_current);
				 GetToken();
				 break;
			 }
			 op_top = op_stack.top();
			 // the operator on the stack top which has a lower precedence
			 if(GetPrecedence(op_top) < GetPrecedence(op_current)){
				 op_stack.push(op_current);
				 GetToken();
			 }
			 else{
				 // pop two variable for build a substree
				 if(var_stack.empty()) parser_exit(EXPR_ERROR); 
				 var1 = var_stack.top();
				 var_stack.pop();
				 if(var_stack.empty()) parser_exit(EXPR_ERROR);
				 var2 = var_stack.top();
				 var_stack.pop();
				 op_stack.pop();

				 // set the link in the ast
				 AST::SetParent(op_top,var2);
				 AST::SetSibling(var2,var1);

				 // push the expression back
				 var_stack.push(op_top);

				 // delete the tnode for the next round for reusing the operator
				 delete op_current;
			 }
			 break;

	    // always push for (
		case ROUND_BRACKET_L:
			op_current = MatchOp();
			op_stack.push(op_current);
			GetToken();
			break;

		// case 1: operator on the top of stack is (, then match it and delete ()
		// case 2: other ususal operator, pop it and form a sub-expr and push it back to variable stack
		case ROUND_BRACKET_R:
			op_current = MatchOp();

			// bracket is not balanced
			if(op_stack.empty()) 
			{
				parser_exit(EXPR_ERROR);
				return NULL;
			}
			
			// if it is a (, pop it for matching bracket
			op_top = op_stack.top();
			if(GetPrecedence(op_top) == 1){
				 op_stack.pop();
				 delete op_top;
				 delete op_current;
				 GetToken();
				 break;
			}
			// else it is + - or *
			else{
				 // pop two variable for build a substree 
				 if(var_stack.empty()) parser_exit(EXPR_ERROR);
				 var1 = var_stack.top();
				 var_stack.pop();
				 if(var_stack.empty()) parser_exit(EXPR_ERROR); 
				 var2 = var_stack.top();				 
				 var_stack.pop();
				 op_stack.pop();

				 // set the link in the ast
				 AST::SetParent(op_top,var2);
				 AST::SetSibling(var2,var1);

				 // push the expression back
				 var_stack.push(op_top);

				 // delete the tnode for the next round for reusing the operator
				 delete op_current;
				 break;
			}
		default:
			 parser_exit(EXPR_ERROR);
		}
	}

	// pop all the expression and form the tree
	while(!op_stack.empty()){
		// pop two sub-exprs on the stack and pop one operator
		if(var_stack.empty()) parser_exit(EXPR_ERROR);
		var1 = var_stack.top();
		var_stack.pop();
		if(var_stack.empty()) parser_exit(EXPR_ERROR);
		var2 = var_stack.top();				 
		var_stack.pop();
		op_top = op_stack.top();
		op_stack.pop();
		// set the link in the AST
		AST::SetParent(op_top,var2);
		AST::SetSibling(var2,var1);

		// push the expression back
		var_stack.push(op_top);
	}

	TNode* p_expr_return = var_stack.top();
	var_stack.pop();
	if(!var_stack.empty()) parser_exit(EXPR_ERROR);
	return p_expr_return;
}

void GetToken(){
	// check if it is end of the file
	if(parser_current_position == parser_program_text.size()) {
		parser_token_type = END;
		parser_token = "";
		return;
	}

	// skip the front useless delimiter
	while(parser_program_text.at(parser_current_position) == ' ' || 
		parser_program_text.at(parser_current_position) == '\t' ||
		parser_program_text.at(parser_current_position) == '\n' ||
		parser_program_text.at(parser_current_position) == '\0' ||
		// carriage return
		parser_program_text.at(parser_current_position) == 13
		){
			// still need to check the end of file
			if(parser_current_position == parser_program_text.size() - 1) {
				parser_token_type = END;
				parser_token = "";
				return;
			}
			parser_current_position++;
	}

	// extract the useful operators
	switch(parser_program_text.at(parser_current_position)){
	case ';':
		parser_token_type = SEMICOLON;
		parser_token = ";";
		parser_current_position++;
		return;
	case '+':
		parser_token_type = ADD;
		parser_token = "+";
		parser_current_position++;
		return;
	case '-':
		parser_token_type = MINUS;
		parser_token = "-";
		parser_current_position++;
		return;
	case '*':
		parser_token_type = MULTIPLY;
		parser_token = "*";
		parser_current_position++;
		return;
	case '=':
		parser_token_type = EQUAL;
		parser_token = "=";
		parser_current_position++;
		return;
	case '(':
		parser_token_type = ROUND_BRACKET_L;
		parser_token = "(";
		parser_current_position++;
		return;
	case ')':
		parser_token_type = ROUND_BRACKET_R;
		parser_token = ")";
		parser_current_position++;
		return;
	case '{':
		parser_token_type = CURLY_BRACKET_L;
		parser_token = "{";
		parser_current_position++;
		return;
	case '}':
		parser_token_type = CURLY_BRACKET_R;
		parser_token = "}";
		parser_current_position++;
		return;
	default:
		if(IsDigit(parser_program_text.at(parser_current_position))) parser_token_type = CONSTANT;
		else if(IsCharacter((parser_program_text.at(parser_current_position)))) parser_token_type = VARIABLE;
		else parser_exit(TOKEN_ERROR);
	}// end switch

	int count = 0;
	char temp;
	do{
		temp = parser_program_text.at(count+parser_current_position);
		if(parser_token_type == CONSTANT){
			if(IsCharacter(temp)) 
			{
				parser_exit(TOKEN_ERROR);
				return;
			}
		}
		if(!IsText(temp)) break;
		count++;
	}while((count + parser_current_position) < parser_program_text.size());
	
	parser_token = parser_program_text.substr(parser_current_position,count);
	parser_current_position += count;
}

void parser_exit(ErrorType error_type){
	stringstream ss_error;
	switch(error_type){
	case FILE_ERROR:
		ss_error << "parser file error!";
		break;
	case TOKEN_ERROR:
		ss_error << "parser token error!";
		break;
	case PROC_ERROR:
		ss_error << "parser procedure match error!";
		break;
	case STMTLIST_ERROR:
		ss_error << "parser stmtlist match error!";
		break;
	case STMT_ERROR:
		ss_error << "parser statement match error!";
		break;
	case ASSIGN_ERROR:
		ss_error << "parser assignment match error!";
		break;
	case CALL_ERROR:
		ss_error << "parser call match error!";
		break;
	case WHILE_ERROR:
		ss_error << "parser while match error!";
		break;
	case IF_ERROR:
		ss_error << "parser if match error!";
		break;
	case EXPR_ERROR:
		ss_error << "parser expression match error!";
		break;
	}
	ss_error << "error occur near statement number: " << parser_stmt_num;
	cout << ss_error.str() << endl;
	getchar();
	exit(1);
}

